\rsec{Apêndice}
\newtheorem*{mydef}{Definição}
\newtheorem*{myteo}{Teorema}

Esta seção é dedicada a prover ao leitor algumas definições e explicações
matemáticas com as quais ele não pode estar habituado.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Matricial}

Neste trabalho, definimos um vetor como sendo uma matriz $n \times 1$, o
vetor-coluna.

\begin{mydef}
Uma matriz $A_{n \times n}$ é dita \textbf{estocástica} quando todas as suas
entradas são não-negativas e em cada linha a soma de suas entradas é igual à 1.
\\
\end{mydef}

\begin{mydef}
Uma matriz $A_{n \times n}$ é dita \textbf{irredutível} se e somente se o grafo
direcionado que ela representa é fortemente conexo. Em outras palavras, se para
cada par de índices (i, j) existe uma sequência de entradas em $A$ tal que
$a_{i{k_1}}a_{{k_1}{k_2}}...a_{{k_t}j} \neq 0$. Equivalentemente, $A$ é
irredutível se para qualquer matriz de permutação $P$,
$$
P'AP \neq 
\begin{pmatrix} X & Y \\ 0 & Z \end{pmatrix},
\mbox{onde $X$ e $Z$ são quadradas}
$$
\\
\end{mydef}

\begin{mydef}
Uma matriz $A_{n \times n}$ é dita \textbf{periódica} se, para algum inteiro $k
\geq 2$, $A^k = A$. Caso não exista tal $k$, a matriz é dita
\textbf{aperiódica}.
\\
\end{mydef}

\begin{mydef}
Uma matriz $A_{n \times n}$ é dita \textbf{semi-definida positiva} se, para
qualquer vetor $v_{n \times 1}$, $$v'Av \geqslant 0$$
\\
\end{mydef}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Processos Estocásticos}

\begin{mydef}
Um \textbf{processo estocástico} é um conjunto de variáveis
aleatórias ${\{X_t\}}_{t = 0}^\infty$ que contêm um espaço de estados
$\{S_1, S_2, ..., S_n\}$
em comum. O parâmetro $t$ é geralmente associado ao tempo e $X_t$ representa o
estado do processo no tempo $t$. No contexto do \textit{PageRank} consideraremos
o tempo discreto.
\\
\end{mydef}

\begin{mydef}
Uma \textbf{cadeia de Markov} é um processo estocástico que satisfaz
a propriedade de Markov
$$
P(X_{t+1} = S_j | X_t = S_{i_{t}}, X_{t-1} = S_{i_{t-1}}, \ldots, X_0 = S_{i_{0}})
= P(X_{t+1} = S_j | X_t = S_{i_{t}})
$$

para cada $t = 0, 1, 2 \ldots$. A notação $P(E|F)$ denota probabilidade
condicional do evento $E$ ocorrer dado o acontecimento do evento $F$.

A \textbf{propriedade de Markov} garante que o processo não possui memória. As
transições de estado ao longo do tempo dependem apenas do estado atual, sendo
sua história irrelevante. O processo do usuário aleatório na web é uma cadeia de
Markov.
\\
\end{mydef}

\begin{mydef}
A \textbf{probabilidade de transição} $p_{ij}(t) = P(X_t = S_j | X_{t-1} = S_i)$
é a probabilidade de mudança do estado $S_i$ para o estado $S_j$ no tempo $t$.
\\
\end{mydef}

\begin{mydef}
Numa cadeia de Markov, um estado $S_j$ é \textbf{acessível} de um estado $S_i$,
ou $S_i \rightarrow S_j$, quando num instante o estado atual é $S_i$, e após uma
quantidade finita de transições é possível estar no estado $S_j$.
Matematicamente, $P(X_{n+k} = S_j | X_k = S_i) = p_{ij}^{(n)} > 0$
\\
\end{mydef}

\begin{mydef}
Numa cadeia de Markov, um estado $S_i$ se \textbf{comunica} com um estado $S_j$
quando $S_i \leftrightarrow S_j$.
\\
\end{mydef}

\begin{mydef}
Uma cadeia de Markov é dita \textbf{irredutível} quando a matriz de transição
$P$ que representa a cadeia é irredutível.
\\
\end{mydef}

\begin{mydef}
Um \textbf{vetor de distribuição de probabilidade} (ou vetor de probabilidade),
é definido como um vetor linha não negativo $p' = (p_1, p_2, ... , p_n)$ onde
$\sum_k p_k = 1$
\\
\end{mydef}

\begin{mydef}
Um vetor de probabilidade \textbf{estacionário} para uma cadeia de Markov, cuja
matriz de transição é $P$, é um vetor $\pi'$ tal que $\pi' = \pi'P$
\\
\end{mydef}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\rssec{Álgebra Linear}

\begin{mydef}
Um \textbf{autovetor} de uma matriz $A_{n \times n}$ é um vetor não nulo que,
quando multiplicado por $A$, resulta num vetor que preserva a direção do vetor
original, diferindo apenas de um escalar. Matematicamente, $v$ é um autovetor
da matriz $A$ se:
$$
Av = \lambda v
$$
O escalar $\lambda$ é denominado o \textbf{autovalor} associado à $v$.
\\
\end{mydef}

\begin{myteo}
\textbf{(Perron–Frobenius)} Uma matriz real $A_{n \times n}$ com todas as
entradas positivas possui um único autovalor dominante positivo, sendo seu
autovetor associado composto estritamente por entradas positivas.
\end{myteo}


